package com.study.leetcode;

import java.util.*;

public class Solution_107 {
    public static List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        levelOrderBottom(root, result, 0);
        Collections.reverse(result);
        return result;
    }

    public static void levelOrderBottom(TreeNode root, List<List<Integer>> result, int deep) {
        if (root != null) {
            if (result.size() < deep + 1) {
                result.add(new ArrayList<>());
            }
            result.get(deep).add(root.val);
            levelOrderBottom(root.left, result, deep + 1);
            levelOrderBottom(root.right, result, deep + 1);
        }
    }

    public static List<List<Integer>> levelOrderBottom1(TreeNode root) {
        LinkedList<List<Integer>> result = new LinkedList<>();
        if (root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> oneLevel = new ArrayList<>();
            // 每次都取出一层的所有数据
            int count = queue.size();
            for (int i = 0; i < count; i++) {
                TreeNode node = queue.poll();
                if (node != null) {
                    oneLevel.add(node.val);
                    if (node.left != null) {
                        queue.add(node.left);
                    }
                    if (node.right != null) {
                        queue.add(node.right);
                    }
                }
            }
            // 每次都往队头塞
            result.addFirst(oneLevel);
        }
        return result;
    }

    public static void main(String[] args) {
        /**
         *          1
         *      2       3
         *   4   5    6   7
         *  8
         *
         */
        TreeNode node8 = new TreeNode(8);
        TreeNode node7 = new TreeNode(7);
        TreeNode node6 = new TreeNode(6);
        TreeNode node5 = new TreeNode(5);
        TreeNode node4 = new TreeNode(4, node8, null);

        TreeNode node3 = new TreeNode(3, node6, node7);
        TreeNode node2 = new TreeNode(2, node4, node5);
        TreeNode node1 = new TreeNode(1, node2, node3);
        List<List<Integer>> lists = levelOrderBottom1(node1);
        System.out.println("lists = " + lists);

    }
}
